In pattern recognition and signal processing information is classified according to general categories, all of them having different sets of theories and algorithms to handle them. Two classifications of relevance for this invention are:    a) The dimensionality of the signals to analyze:            One-dimensional signals are quite widespread. Examples are audio signals or any time series of one variable.        Two-dimensional signals are e.g. images which have two spatial dimensions.        Examples of three-dimensional signals are video signals which add the time dimension to an image signal.            b) Discrete or continuous signals:            A signal can assume any real or complex value in each of its dimensions or show only discrete (quantized) values. The discretization can happen on two levels:        The signal is only known at discrete spots of one or more dimensions, i.e. the signal is sampled.        The values of the signal are quantized.        
The present invention preferably relates to discrete one-dimensional signals which are sampled and quantized.
The most common way to solve the problem of fault-tolerant search was the application of the so-called “edit distance” in combination with dynamic programming (DP). The edit distance is a measure or dimension that describes the distance between two strings S1 and S2. The distance is defined to be the number of insertions, deletions and variations that are required to transform e.g. a string S1 into a string S2. These required transformations are computed by applying the idea of dynamic programming, which is commonly based on a “divide-and-conquer” algorithm:
A divide-and-conquer algorithm subdivides the original problem into smaller independent problem partitions and tries to find a solution for those smaller partitions first. In the following steps the divide-and-conquer algorithm tries to solve the problem for bigger partitions by taking and combining the solutions of the already edited smaller problem partitions. Finally, the algorithm tries to combine these solutions to find a solution for the original problem without any partitioning.
The implementation of an edit distance in combination with dynamic programming (DP) is strictly dependent on the problem context it is applied in. In most cases the implementation cannot be kept untouched if the problem context changes, because the implementation of the edit distance is usually specialized for a particular problem context. Especially the realization of a Dynamic Programming (DP) algorithm is in most cases highly specialized for the particular problem. Two essential problems may arise in the context of DP:                1.) Not every problem can be partitioned so that it can be solved with DP.        2.) The number of conceivable problem partitions is too great. The runtime of DP would not be very convenient as an obvious consequence.        
In the context of a fault-tolerant search, the edit distance represents in combination with DP a specialized solution to measure the similarity of two strings S1 and S2. It is obvious that especially under consideration of 2.) some preconditions need to be defined to apply the edit distance in an acceptable runtime if the following faults occurring during comparison of S1 and S2 shall be tolerated:                Characters of the string may (however) be varied        Additional characters may (wherever) be inserted        Characters may (if any and wherever) be missing        
Many possibilities exists to define preconditions to keep the runtime low, but in most cases either the tolerance or the search accuracy increases anyhow.
Such a method is e.g. disclosed in the European Patent Application EP 1 093 109 A1 “Verfahren zum Erkennen und Auswählen einer Tonfolge, insbesondere eines Musikstücks”. In this document a method is disclosed to compare a first sequence of notes with a second sequence of notes, to determine the similarity between said two sequences. The disclosed method is based on a median and on comparing the tone duration and the variation of adjacent successive tones in both sequences.